import javafx.beans.binding.StringBinding;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-03-30
 * Time: 22:40
 */
public class Test2 {

    //-------------------------------------------Day11-----------------------------------------------
    //No.1
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int max = 0;
        int tmp = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >> i) & 1) == 1) {
                tmp++;
            } else {
                max = tmp > max ? tmp : max;
                tmp = 0;
            }
        }
        System.out.println(max);
    }

    //No.2 二叉树公共祖先没能按时提交


    //-------------------------------------------Day12-----------------------------------------------
    // No.1.2
    public static void main2(String[] args) {
        // 知识点1：HashMap键值为空
//        HashMap<String,String> hashMap = new HashMap<>();
//        hashMap.put(null,null);


        // 知识点2：byte间接相加问题

    }

    //No.3_妙啊！！！
    public int binInsert(int n, int m, int j, int i) {
        // write code here
        m = m << j;
        return m | n;
    }

    //No.4
    public static boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main3(String[] args) {
        // 输入
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        // minPrime数组存储结果
        int[] minPrime = new int[2];
        // n<=1000 初始值取1000
        int minLen = 1000;

        // 这里的循环仅需判断一半即可
        for (int i = 2; i <= n / 2; i++) {
            // 如果i是素数，n-i是素数，并且二者距离小于当前最小距离，就更新结果数组
            if (isPrime(i) && isPrime(n - i) && n - i - i < minLen) {
                minPrime[0] = i;
                minPrime[1] = n - i;
                minLen = n - i - i;
            }
        }

        System.out.println(minPrime[0]);
        System.out.println(minPrime[1]);

    }


    //-------------------------------------------Day13-----------------------------------------------
    //No.1:优化前
    public static void main4(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        StringBuilder[] sb = new StringBuilder[str.length()];
        for (int i = 0; i < str.length(); i++) {
            sb[i] = new StringBuilder();
        }
        int count = 0;

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                count++;
                i++;
            }

            if (str.charAt(i) == '"') {
                i++;
                while (i < str.length() && str.charAt(i) != '"') {
                    sb[count].append(str.charAt(i));
                    i++;
                }
                i++;
            }
            if (i < str.length() && str.charAt(i) != ' ' && str.charAt(i) != '"') {
                while (i < str.length() && str.charAt(i) != ' ') {
                    sb[count].append(str.charAt(i));
                    i++;
                }
                if (i < str.length()) {
                    count++;
                }
            } else {
                i--;
            }

        }

        System.out.println(count + 1);
        for (int i = 0; i <= count; i++) {
            System.out.println(sb[i]);
        }
    }

    // No.1:优化后
    public static void main5(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        StringBuilder[] sb = new StringBuilder[str.length()];
        for (int i = 0; i < str.length(); i++) {
            sb[i] = new StringBuilder();
        }
        int count = 0;
        int i = 0;
        while (i < str.length()) {
            if (str.charAt(i) == ' ') {
                count++;
                i++;
            }

            if (str.charAt(i) == '"') {
                i++;
                while (i < str.length() && str.charAt(i) != '"') {
                    sb[count].append(str.charAt(i));
                    i++;
                }
                i++;
            }
            if (i < str.length() && str.charAt(i) != ' ' && str.charAt(i) != '"') {
                while (i < str.length() && str.charAt(i) != ' ') {
                    sb[count].append(str.charAt(i));
                    i++;
                }
            }
        }
        System.out.println(count + 1);
        for (int j = 0; j <= count; j++) {
            System.out.println(sb[j]);
        }
    }


//        for (int i = 0; i < str.length(); i++) {
//            if (str.charAt(i)==' ') {
//                count++;
//                i++;
//            }
//
//            if (str.charAt(i) == '"') {
//                i++;
//                while (i<str.length() && str.charAt(i)!='"') {
//                    sb[count].append(str.charAt(i));
//                    i++;
//                }
//                i++;
//            }
//           if (i<str.length() && str.charAt(i)!=' ' && str.charAt(i)!='"') {
//               while (i<str.length() && str.charAt(i)!=' ') {
//                   sb[count].append(str.charAt(i));
//                   i++;
//               }
//               count++;
//           } else {
//               i--;
//           }
//
//        }

    //No.2:跳石板问题，真滴不会呀！！！
    // 好像得用递归？


    //-------------------------------------------Day14-----------------------------------------------
    // No.1
    public static void main6(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int year = scanner.nextInt();
        int month = scanner.nextInt();
        int day = scanner.nextInt();
        int second = 0;

        if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
            second = 29;
        } else {
            second = 28;
        }

        switch (month) {
            case 1:
                day += 0;
                break;
            case 2:
                day = day + 31;
                break;
            case 3:
                day = day + 31 + second;
                break;
            case 4:
                day = day + 31 + 31 + second;
                break;
            case 5:
                day = day + (31 + 31 + 30) + second;
                break;
            case 6:
                day = day + (31 + 31 + 31 + 30) + second;
                break;
            case 7:
                day = day + (31 + 31 + 31 + 30 + 30) + second;
                break;
            case 8:
                day = day + (31 + 31 + 31 + 30 + 30 + 31) + second;
                break;
            case 9:
                day = day + (31 + 31 + 31 + 30 + 30 + 31 + 31) + second;
                break;
            case 10:
                day = day + (31 + 31 + 31 + 30 + 30 + 31 + 31 + 30) + second;
                break;
            case 11:
                day = day + (31 + 31 + 31 + 30 + 30 + 31 + 31 + 30 + 31) + second;
                break;
            case 12:
                day = day + (31 + 31 + 31 + 30 + 30 + 31 + 31 + 30 + 31 + 30) + second;
                break;
        }
        System.out.println(day);
    }

    // No.2:幸运的袋子.这个也不会啊！！！
    public static void main7(String[] args) {

    }


    //-------------------------------------------Day15-----------------------------------------------
    // No.1
    public static void main8(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int x = scanner.nextInt();
            int count = 0;
            for (int i = 0; i < 32; i++) {
                int tmp = x >> i;
                if ((tmp & 1) == 1) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }

    // No.2 不太清楚原理

    public int findMinimum(int n, int[] left, int[] right) {
        // write code here
        int sum = 0;//存放某种颜色的一只手的手套个数为0的时候，另一只手的手套数量
        int leftSum = 0;
        int rightSum = 0;
        int leftMin = Integer.MAX_VALUE;
        int rightMin = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (left[i] * right[i] == 0) {
                // 统计一只手套为0时，另一只手套的数量
                sum = sum + left[i] + right[i];
            } else {
                // 都不为0时，左手套和
                leftSum += left[i];
                if (leftMin > left[i]) {
                    // 都不为0时，左手套最小
                    leftMin = left[i];
                }
                // 都不为0时，右手套和
                rightSum += right[i];
                if (rightMin > right[i]) {
                    // 都不为0时，右左手套最小
                    rightMin = right[i];
                }
            }
        }
        // 一只手套为0时，另一只手套的数量必须都加上；（为啥+1）
        return sum + Math.min(leftSum - leftMin + 1, rightSum - rightMin + 1) + 1;

    }

    //-------------------------------------------Day16-----------------------------------------------
    // No.1
    public static boolean perfectNum(int x) {
        int sum = 0;
        for (int i = 1; i < x; i++) {
            if (x % i == 0) {
                sum += i;
            }
        }
        if (sum == x) {
            return true;
        }
        return false;
    }

    public static void main9(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int count = 0;

        for (int i = 1; i <= n; i++) {
            if (perfectNum(i)) {
                count++;
            }
        }
        System.out.println(count);

    }

    // No.2
    // 写个遍历函数
    public static void printPoker(String[] array) {
        for (String x:array) {
            System.out.print(x+" ");
        }
    }

    public static void main10(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入字符串
        String str = scanner.nextLine();
        String[] array = str.split("-");
        // 左手牌
        String[] left = array[0].split(" ");
        // 右手牌
        String[] right = array[1].split(" ");

        // 进行比较(将牌数同和不相同区分比较)
        if (left.length == right.length) {
            // 牌数相等
            // 个子和个子

            // 判断大小王情况(已知不会出现相同的两手牌)
            if (left[0].equals("JOKER")) {
                printPoker(left);
                return;

            } else if (right[0].equals("JOKER")) {
                printPoker(right);
                return;

            } else if (left[0].equals("joker")) {
                printPoker(left);
                return;

            } else if (right[0].equals("joker")) {
                printPoker(right);
                return;

            } else if (left[0].equals("2")) {
                printPoker(left);
                return;

            } else if (right[0].equals("2")) {
                printPoker(right);
                return;

            } else if (left[0].equals("A")) {
                printPoker(left);
                return;

            } else if (right[0].equals("A")) {
                printPoker(right);
                return;

            } else if (left[0].equals("K")) {
                printPoker(left);
                return;

            } else if (right[0].equals("K")) {
                printPoker(right);
                return;

            } else if (left[0].equals("Q")) {
                printPoker(left);
                return;

            } else if (right[0].equals("Q")) {
                printPoker(right);
                return;

            } else if (left[0].equals("J")) {
                printPoker(left);
                return;

            } else if (right[0].equals("J")) {
                printPoker(right);
                return;

            } else if (left[0].equals("10")) {
                printPoker(left);
                return;

            } else if (right[0].equals("10")) {
                printPoker(right);
                return;
            }

            // 一般情况：包括顺子
            // 10和其它比较会出问题
            if (left[0].compareTo(right[0]) > 0) {
                printPoker(left);
                return;
            } else {
                printPoker(right);
                return;
            }


        } else {
            // 牌数不等
            // 存在対王情况
            if (left.length==2) {
                if (left[0].equals("JOKER") || left[0].equals("joker")) {
                    printPoker(left);
                    return;
                }
            }
            if (right.length==2) {
                if (right[0].equals("JOKER") || right[0].equals("joker")) {
                    printPoker(right);
                    return;
                }
            }
            if (left.length==4) {
                // 存在炸弹情况
                printPoker(left);
                return;
            }
            if (right.length==4) {
                printPoker(right);
                return;
            }
        }
        System.out.println("ERROR");

    }

    //-------------------------------------------Day17-----------------------------------------------

    // No.1 杨辉三角变形，测试用例很大，运行超时
    public static void main11(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        List<List<Integer>> lists = new ArrayList<>();

        List<Integer> row = new ArrayList<>();
        row.add(1);
        lists.add(row);

        // 从第二行开始，为每一行添加数字
        for (int i = 1; i < n; i++) {
            // 由于当前行和下一行有关系，这里获取前一行，并创建新的一行。
            List<Integer> preRow = lists.get(i - 1); //前一行
            List<Integer> curRow = new ArrayList<>();//新一行

            // 每一行第一个数字为1
            curRow.add(1);

            // 中间数
            int centrlNums = 2 * (i + 1) - 1 - 1;
            int size = preRow.size();
            for (int j = 1; j < centrlNums; j++) {
                int sum = 0;
                if ((j - 1 - 1) >= 0) {
                    sum += preRow.get(j - 1 - 1);
                }
                // 经分析：j-1一定存在
                sum += preRow.get(j - 1);
                if (j < size) {
                    sum += preRow.get(j);
                }
                curRow.add(sum);
            }
            // 每一行最后一个数字为1
            curRow.add(1);
            // 将构造好的行添加到lists中
            lists.add(curRow);
        }
        int numSize = lists.get(n - 1).size() / 2;
        List<Integer> nRow = lists.get(n - 1);
        int i = 0;
        for (i = 0; i <= numSize ; i++) {
            if (nRow.get(i) % 2 == 0) {
                System.out.println(i + 1);
                break;
            }
        }
        if (i > numSize) {
            System.out.println(-1);
        }

//        测试打印
//        for (int i = 0; i < lists.size(); i++) {
//            for (int j = 0; j < lists.get(i).size(); j++) {
//                System.out.print(lists.get(i).get(j)+" ");
//            }
//            System.out.println();
//        }
    }

    // No.2
    public static void main12(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String dest = scanner.nextLine();
        dest = dest.toLowerCase();
        char src = scanner.nextLine().charAt(0);

        int count =0;
        for (int i = 0; i < dest.length(); i++) {
            if (src==dest.charAt(i)) {
                count++;
            }
        }
        System.out.println(count);

    }

    //-------------------------------------------Day18-----------------------------------------------
    // No.1 斐波那契数列（简单）

    // No.2 字符串通配符，很难！！！

    //-------------------------------------------Day19-----------------------------------------------
    // No.1
    public static void main13 (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        while (n!=0) {
            int empty = n; //空瓶
            int bottle = 0; // 喝到的水

            while (empty>=3) {
                bottle += empty/3;
                empty = empty/3+empty%3;
            }
            if (empty==2) {
                bottle+=1;
            }
            System.out.println(bottle);
            n = scanner.nextInt();
        }
    }

    // No.2
    public static void main14(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();

        // 交换，使str1引用为较短字符串
        if (str1.length()>str2.length()) {
            String tmpStr = str1;
            str1 = str2;
            str2 = tmpStr;
        }

        // 记录最长子串长度
        int len = 0;
        // 记录最长子串初始位置
        int start = 0;

        for (int i = 0; i < str1.length(); i++) {
            // 记录当前i下标
            int curi = i;
            for (int j = 0; j < str2.length(); j++) {
                int curj = j;
                // 创建临时变量，作为当前趟数下子串长度
                int tmp = 0;

                char ch1 = str1.charAt(i);
                char ch2 = str2.charAt(j);
                while (i<str1.length() && j<str2.length() && ch1==ch2) {
                    tmp++;
                    i++;
                    j++;
                    if (i<str1.length() && j<str2.length()) {
                        ch1 = str1.charAt(i);
                        ch2 = str2.charAt(j);
                    }
                }

                // i归位，j归位，继续向j后方查找
                i= curi;
                j= curj;
                if (tmp>len) {
                    // 如果此趟序列长度大于已知最大长度，修改len，同时记录起始下标
                    start = i;
                    len = tmp;
                }
            }
        }

        // 变历打印
        for (int i = start; i < start+len ; i++) {
            System.out.print(str1.charAt(i));
        }

        // 打印测试
        System.out.println();
        System.out.println("最长子串起始位置："+start);
        System.out.println("最长子串长度："+len);

//        oegdlsxizdvkxmjxowdnkkuzwgsjwzmdybnjtevpmmgrivrobfiodnntkvhafczjbnngrxevnvbomtgegfeelhlsxgncxuigdwiohrs
//        nzsgfqehjfuzwgoutejskvieqhxhhbachtuqzyhptnaktqbbfxevuqlkga
//        uzwg
//        最长子串起始位置：10
//        最长子串长度：4

    }

    //-------------------------------------------Day20-----------------------------------------------
    // No.1
    public static void main15(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入
        String str = scanner.nextLine();
        // 反转操作
        int start = 0;
        int end = str.length()-1;
        char[] array = str.toCharArray();
        while (start<end) {
            char s = array[start];
            array[start] = array[end];
            array[end] = s;
            start++;
            end--;
        }
        String dest = new String(array);
        System.out.println(dest);

    }

    // No.2 昨天写过
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        // 始终让str1指向较短的字符串
        if (str1.length()>str2.length()) {
            String tmpStr = str1;
            str1 = str2;
            str2 = tmpStr;

        }

        int maxLen = 0;
        for (int i = 0; i < str1.length(); i++) {
            int curi = i;
            for (int j = 0; j < str2.length(); j++) {
                int curj = j;

                int tmp = 0;
                char ch1 = str1.charAt(i);
                char ch2 = str2.charAt(j);
                while (i<str1.length() && j<str2.length() && ch1==ch2) {
                    i++;
                    j++;
                    tmp++;
                    if (i<str1.length() && j<str2.length()) {
                        ch1 = str1.charAt(i);
                        ch2 = str2.charAt(j);
                    }
                }

                i = curi;
                j = curj;
                if (tmp>maxLen) {
                    maxLen = tmp;
                }
            }
        }
        System.out.println(maxLen);
    }


}